﻿using System;
using System.Collections.Generic;
using System.Text;
using PPClasses;

namespace PortalPlan.Solvers
{
    internal class Flow : Solver
    {
        private int NextNodeID = 0;
        private Dictionary<string, int> Nodes = new Dictionary<string, int>();
        private Dictionary<int, Pair> PairFor = new Dictionary<int, Pair>();

        public override bool CanThread
        {
            get { return true; }
        }

        private bool NodeExists(string name)
        {
            return Nodes.ContainsKey(name);
        }

        private int AddNode(string name, Pair pair)
        {
            if (NodeExists(name))
                return NodeIDFor(name);

            Nodes.Add(name, NextNodeID);
            PairFor.Add(NextNodeID, pair);
            System.Diagnostics.Debug.Print("Add node " + name + " (" + NextNodeID + ")");
            return NextNodeID++;
        }

        private int NodeIDFor(string name)
        {
            System.Diagnostics.Debug.Assert(NodeExists(name));
            return Nodes[name];
        }

        private class Link
        {
            public int From;
            public int To;
            public int Capacity;
        }

        private List<Link> Links = new List<Link>();
        private List<int> Edges = new List<int>();

        private int UNBOUNDED = 1000000; // a "big" number

        private void AddLink(int from, int to, int upperBound)
        {
            Links.Add(new Link() {From = from, To = to, Capacity = upperBound});
            System.Diagnostics.Debug.Print("Add link " + from + "->" + to + " @ " +
                                           (upperBound == UNBOUNDED ? "∞" : upperBound.ToString()));
        }

        private void SetupNodes()
        {
            //char[] letters = new[] { 'A', 'B', 'C', 'D', 'E' };
            int id_s = AddNode("S", null);
            int id_t = AddNode("T", null);

            int npt = PortalPoints.Count;
            UNBOUNDED = npt * 1000;

            // every pairing gets a node
            System.Diagnostics.Debug.Print("");

            for (int a = 0; a < npt; a++)
            {
                for (int b = a + 1; b < npt; b++)
                {
                    //string name = letters[a] + "," + letters[b];
                    string name = a + "," + b;
                    int id = AddNode(name, new Pair(a, b));
                    AddLink(id_s, id, UNBOUNDED);
                }
            }

            // additional nodes for links that block others
            System.Diagnostics.Debug.Print("");
            int firstBlocker = int.MaxValue;
            bool[] blocked = new bool[NextNodeID];
            for (int a = 0; a < npt; a++)
            {
                for (int b = a + 1; b < npt; b++)
                {
                    //string fromName = letters[a] + "," + letters[b];
                    string fromName = a + "," + b;
                    int id_from = NodeIDFor(fromName);
                    int blocksid = -1;
                    for (int c = a + 1; c < npt; c++)
                    {
                        for (int d = c + 1; d < npt; d++)
                        {
                            System.Diagnostics.Debug.Print("LC: " + a + " " + b + " " + c + " " + d);
                            if (LinesCross(new Pair(a, b), new Pair(c, d)))
                            {
                                string toName = c + "," + d;
                                System.Diagnostics.Debug.Print(fromName + " blocks " + toName);
                                if (blocksid == -1)
                                {
                                    string name = "B" + a + "," + b;
                                    blocksid = AddNode(name, null);
                                    AddLink(id_from, blocksid, UNBOUNDED);
                                    AddLink(blocksid, id_t, 1);
                                    if (firstBlocker == int.MaxValue)
                                        firstBlocker = blocksid;
                                    blocked[id_from] = true;
                                }
                                int id_to = NodeIDFor(toName);
                                blocked[id_to] = true;
                                AddLink(id_to, blocksid, UNBOUNDED);
                            }
                        }
                    }


                }
            }
            System.Diagnostics.Debug.Print("");

            for (int i = 0; i < blocked.Length; i++)
            {
                if (i == id_s || i == id_t)
                    continue;
                if (!blocked[i])
                    AddLink(i, id_t, 1);
            }
            System.Diagnostics.Debug.Print("");

            edmondsKarp(id_s, id_t, firstBlocker);

        }

        // Converted from the Java at http://en.wikibooks.org/wiki/Algorithm_implementation/Graphs/Maximum_flow/Edmonds-Karp
        public void edmondsKarp(int s, int t, int firstBlocker)
        {
            int n = Nodes.Count;
            List<int>[] E = new List<int>[n]; // neighbour list
            for (int i = 0; i < n; i++)
                E[i] = new List<int>();

            int[,] C = new int[n,n]; // capacity list

            foreach (Link l in Links)
            {
                E[l.From].Add(l.To);
                C[l.From, l.To] = l.Capacity;
            }

            // Residual capacity from u to v is C[u][v] - F[u][v]
            int[,] F = new int[n,n];
            int f = 0; // initial flow is zero
            while (true)
            {
                int[] P;

                int m = BFS(out P, n, C, E, s, t, F);
                if (m == 0)
                    break;
                f += m;

                // Backtrack search, and write flow
                int v = t;
                while (v != s) // or != s?
                {
                    int u = P[v];
                    F[u, v] += m;
                    F[v, u] -= m;
                    v = u;
                }
            }

            System.Diagnostics.Debug.Print("");
            System.Diagnostics.Debug.Print("f is " + f);
            System.Diagnostics.Debug.Print("");

            // Turn flows into edges to link
            for (int x = 0; x < n; x++)
            {
                if (x == s || x == t)
                    continue;

                if (F[s, x] != 1)
                    continue;

                bool ok = x != s && x != t && x < firstBlocker;
                Pair pair = PairFor[x];
                System.Diagnostics.Debug.Assert(ok == (pair != null));
                if (ok)
                {
                    System.Diagnostics.Debug.Assert(pair != null);
                    System.Diagnostics.Debug.Print("Link " + pair.a + "," + pair.b);
                    BestPairs.Add(pair);
                }
            }
        }

        private int BFS(out int[] P, int n, int[,] C, List<int>[] E, int s, int t, int[,] F) // returns "M"
        {
            P = new int[n]; // Parent table
            for (int i = 0; i < n; i++)
                P[i] = -1;
            P[s] = s;
            int[] M = new int[n]; // Capacity of found path to node
            M[s] = int.MaxValue;
            // BFS queue
            Queue<int> Q = new Queue<int>();
            Q.Enqueue(s);
            while (Q.Count > 0)
            {
                int u = Q.Dequeue();
                foreach (int v in E[u])
                {
                    // There is available capacity,
                    // and v is not seen before in search
                    if (C[u, v] - F[u, v] > 0 && P[v] == -1)
                    {
                        System.Diagnostics.Debug.Assert(u != v);
                        P[v] = u;
                        M[v] = Math.Min(M[u], C[u, v] - F[u, v]);
                        if (v != t)
                            Q.Enqueue(v); // not at the final node yet
                        else
                        {
                            return M[t];
                        }
                    }
                }
            }
            return 0;
        }

        public Flow(List<Portal> points) : 
            base(points)
        {
            SetupNodes();
        }

        public override void GoGoGo()
        {
            CompletelyDone = true;
            PercentDone = 100;
        }

        public override string StatusText()
        {
            return "Graph has " + Nodes.Count + " nodes, " + Links.Count + " links.  Solution has " + BestPairs.Count +
                   " links.";
        }
    }
}
